package top101K.linkedList;

/**
 * @Author quan
 * @Description 合并排序列表
 * @Date 2023/7/28 20:59
 */
public class Demo4_Merge {
    /**
     * 基础做法：迭代法：算法复杂度太高不通过
     * @param pHead1 子链表1的头结点
     * @param pHead2 子链表2的头结点
     * @return 返回合并后排序链表的头结点
     */
//    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
//        //base case1:两个子链表都为null，直接返回null
////        if(pHead1 == null && pHead2 == null){
////            return null;
////        }
//        //base case2：有一个链表为null，则另一个子链表就是合并后的链表
//        if(pHead1 == null){
//            return pHead2;
//        }
//        if(pHead2 == null){
//            return pHead1;
//        }
//        //case3:这两个子链表都不为null
//        //(1)创建合并后链表的虚拟头结点
//        ListNode dummyHead = new ListNode(-1);
//        ListNode tail = dummyHead;
//        //(2)双指针开始遍历
//        //当两个子链表都没遍历完
//        while (pHead1!=null && pHead2!=null){
//            //比较两个链表的节点的值，将值较小的子链表直接拼接在虚拟头结点后
//            //直接使用两个子链表的头结点后移，因为后面也用不到这两个旧的子链表了
//            //但是合并的新链表的虚拟头结点不能直接后移，而是创建一个和它一样的tail后移，因为最后要返回这个新链表的头结点，就是dummyHead.next
//            if(pHead1.val < pHead2.val){
//                tail.next = pHead1;//连接子链表1
//                tail = pHead1;//更新tail值
//                pHead1 = pHead1.next;//子链表1的节点右移一位
//            }else{
//                //说明pHead2的值小
//                tail.next = pHead2;
//                tail = pHead2;
//                pHead2 = pHead2.next;
//            }
//        }
//        //case 4:说明有一个子链表已经走完了，直接判断并拼接
//        if(pHead1 == null){
//            tail.next = pHead2;
//        }
//        if(pHead2 == null){
//            tail.next = pHead1;
//        }
//        //final:返回最终的头结点
//        return dummyHead.next;
//    }

    /**
     * 递归法
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2){
        //base case:有一个链表为null，直接返回另一个链表
        if(pHead1 == null){
            return pHead2;
        }
        if(pHead2 == null){
            return pHead1;
        }
        //递归调用
        if(pHead1.val < pHead2.val){
            pHead1.next = Merge(pHead1.next,pHead2);
            return pHead1;
        }else{
            pHead2.next = Merge(pHead2.next,pHead1);
            return pHead2;
        }
    }
}
